package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-16 17:17
 */
public class 题库_0010_正则表达式匹配 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    String s = "aa";
    String p = "a*";

    boolean matchWithDp = solution.isMatchWithDp(s, p);
    System.out.println(matchWithDp);
  }

  static
  class Solution {
    public boolean isMatch(String s, String p) {
      if (p == null || p.length() == 0) {
        return s == null || s.length() == 0;
      }
//      return isMatch(s.toCharArray(), 0, p.toCharArray(), 0);
      return isMatchWithDp(s, p);
    }

    /**
     * dp[i][j] 表示 p 的前 i 个字符与 s 的前 j 个字符是否匹配
     * 思路：
     *  1. * 号匹配
     *    1.1 丢弃 .* ，看 p 剩余的前 i - 2 个字符与 s 的前 j 个字符是否匹配（已知）
     *    1.2 如果 s 的第 j 个字符与 p 的第 i - 1（* 号前面的字符）匹配，丢弃 j；看 p 的前 i 个字符与 s 的前 j - 1 个字符是否匹配（已知）
     *  2. 非 * 号匹配
     *    2.1 p 的第 i 个字符与 s 的第 j 个字符匹配，看 p 的前 i - 1 个字符与 s 的前 j - 1 个字符是否匹配
     *    2.2 否则，false
     *  3. 特殊匹配（样例没有，但是用 DP 必须考虑）
     *    s 为空串时，p 的前几个字符可以与之匹配
     * @param s
     * @param p
     * @return
     */
    private boolean isMatchWithDp(String s, String p) {

      int m = p.length() + 1;
      int n = s.length() + 1;
      boolean[][] dp = new boolean[m][n];
      dp[0][0] = true;
      // s 为空串时匹配的特殊情况
      for (int i = 2; i < m; i += 2) {
        if (p.charAt(i - 1) == '*') {
          dp[i][0] = true;
        } else {
          break;
        }
      }

      for (int i = 1; i < m; ++i) {
        // 当前字符后面为 *，必须当做一个整体来看
        if (i < p.length() && p.charAt(i) == '*') {
          continue;
        }
        for (int j = 1; j < n; ++j) {
          if (p.charAt(i - 1) == '*') {
            // * 字符匹配
            dp[i][j] = dp[i - 2][j];
            if (match(p, i - 1, s, j)) {
              dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
          } else {
            // 非 * 字符匹配
            if (match(p, i, s, j)) {
              dp[i][j] = dp[i - 1][j - 1];
            }
          }
        }
      }

      return dp[m - 1][n - 1];
    }

    private boolean match(String p, int i, String s, int j) {
      return (i > 0) && (p.charAt(i - 1) == '.' || p.charAt(i - 1) == s.charAt(j - 1));
    }

    private boolean isMatch(char[] sChs, int si, char[] pChs, int pi) {
      // 模式串下标到达末尾，字符串下标也必须到达末尾
      if (pi == pChs.length) {
        return si == sChs.length;
      }
      boolean answer = false;

      // 判断 * 号
      if (pi + 1 < pChs.length && pChs[pi + 1] == '*') {
        // 匹配 0 个字符
        answer = answer || isMatch(sChs, si, pChs, pi + 2);

        // 至少匹配 1 个字符
        if (si < sChs.length && (pChs[pi] == '.' || pChs[pi] == sChs[si])) {
          answer = answer || isMatch(sChs, si + 1, pChs, pi);
        }
      } else {
        // 不存在 * 号
        if (si < sChs.length && (pChs[pi] == '.' || pChs[pi] == sChs[si])) {
          answer = answer || isMatch(sChs, si + 1, pChs, pi + 1);
        }
      }
      return answer;
    }
  }

}
